#define _CRT_SECURE_NO_WARNINGS 1
//描述
//编一个程序，读入用户输入的一串先序遍历字符串，
//根据此字符串建立一个二叉树（以指针方式存储）。
//例如如下的先序遍历字符串： ABC##DE#G##F### 
//其中“#”表示的是空格，空格字符代表空树。
//建立起此二叉树以后，再对二叉树进行中序遍历，
//输出遍历结果。
//输入描述：
//输入包括1行字符串，长度不超过100。
//示例1
//输入：
//abc##de#g##f###
//输出：
//c b e g d f a
 
#include <stdio.h>
#include<stdlib.h>
typedef char BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

BTNode* CreateTree(char* a, int* pi)
{
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = BuyNode(a[*pi]);
	(*pi)++;

	root->left = CreateTree(a, pi);
	root->right = CreateTree(a, pi);
	return root;
}
//中序
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	//递归
	InOrder(root->left);//左子树
	printf("%c ", root->data);//根
	InOrder(root->right);//右子树
}
int main() {
	char a[100];
	scanf("%s", a);
	int i = 0;
	BTNode* root = CreateTree(a, &i);
	InOrder(root);
	return 0;
}